package com.googlecode.tinyjava.parser.syntaxtree;
import java.util.LinkedList;
import java.util.List;

import com.googlecode.tinyjava.symboltable.*;
import com.googlecode.tinyjava.syntaxtree.*;

public class Parser {
	public static final int _EOF = 0;
	public static final int _ident = 1;
	public static final int _number = 2;
	public static final int _stringconst = 3;
	public static final int _charconst = 4;
	public static final int maxT = 54;

	static final boolean T = true;
	static final boolean x = false;
	static final int minErrDist = 2;

	public Token t;    // last recognized token
	public Token la;   // lookahead token
	int errDist = minErrDist;
	
	public Scanner scanner;
	public Errors errors;

	public SymbolTable symbolTable;
public PackageStatement root;

boolean isDataItemDeclaration() {
	Token x = la;
	if ("final".equals(x.val))
		x = scanner.Peek();
	x = scanner.Peek();
	x = scanner.Peek();
	return ";".equals(x.val) || "=".equals(x.val);
}

boolean isAssignment() {
	Token x = la;
	return "=".equals(x.val);
}

boolean isMethodCall() {
	return "(".equals(la.val);
}



	public Parser(Scanner scanner) {
		this.scanner = scanner;
		errors = new Errors();
	}

	void SynErr (int n) {
		if (errDist >= minErrDist) errors.SynErr(la.line, la.col, n);
		errDist = 0;
	}

	public void SemErr (String msg) {
		if (errDist >= minErrDist) errors.SemErr(t.line, t.col, msg);
		errDist = 0;
	}
	
	void Get () {
		for (;;) {
			t = la;
			la = scanner.Scan();
			if (la.kind <= maxT) {
				++errDist;
				break;
			}

			la = t;
		}
	}
	
	void Expect (int n) {
		if (la.kind==n) Get(); else { SynErr(n); }
	}
	
	boolean StartOf (int s) {
		return set[s][la.kind];
	}
	
	void ExpectWeak (int n, int follow) {
		if (la.kind == n) Get();
		else {
			SynErr(n);
			while (!StartOf(follow)) Get();
		}
	}
	
	boolean WeakSeparator (int n, int syFol, int repFol) {
		int kind = la.kind;
		if (kind == n) { Get(); return true; }
		else if (StartOf(repFol)) return false;
		else {
			SynErr(n);
			while (!(set[syFol][kind] || set[repFol][kind] || set[0][kind])) {
				Get();
				kind = la.kind;
			}
			return StartOf(syFol);
		}
	}
	
	void TinyJava() {
		Expect(5);
		Expect(1);
		root = new PackageStatement(symbolTable.currentScope); 
		Expect(6);
		while (la.kind == 7) {
			ClassStatement classNode = ClassDeclaration();
			root.add(classNode); 
		}
		root.print(); 
	}

	ClassStatement  ClassDeclaration() {
		ClassStatement  classNode;
		Expect(7);
		Expect(1);
		classNode = new ClassStatement(symbolTable.getScope(t.val)); 
		ClassBody(classNode);
		symbolTable.back(); 
		return classNode;
	}

	void ClassBody(ClassStatement classNode) {
		Expect(8);
		while (StartOf(1)) {
			TreeNode node = ClassItemDeclaration();
			classNode.add(node); 
		}
		Expect(9);
	}

	TreeNode  ClassItemDeclaration() {
		TreeNode  node;
		node = null; 
		if (isDataItemDeclaration()) {
			node = DataItemDeclaration();
		} else if (StartOf(2)) {
			node = MethodDeclaration();
		} else SynErr(55);
		return node;
	}

	TreeNode  DataItemDeclaration() {
		TreeNode  node;
		if (la.kind == 10) {
			Get();
		}
		Type();
		Expect(1);
		node = new Assignment(symbolTable.get(t.val)); 
		if (la.kind == 11) {
			Get();
			Expression expression = Expression();
			((Assignment)node).setExpression(expression); 
		}
		Expect(6);
		return node;
	}

	MethodStatement  MethodDeclaration() {
		MethodStatement  method;
		method = null; 
		if (StartOf(3)) {
			method = MethodHeader();
		}
		MethodBlock(method);
		symbolTable.back(); 
		return method;
	}

	void Type() {
		if (StartOf(4)) {
			StdType();
			if (la.kind == 15) {
				Get();
				Expect(16);
			}
		} else if (la.kind == 17) {
			Get();
		} else SynErr(56);
	}

	Expression  Expression() {
		Expression  expression;
		expression = OrElseExpression();
		return expression;
	}

	MethodStatement  MethodHeader() {
		MethodStatement  method;
		ReturnType();
		Expect(1);
		method = new MethodStatement(symbolTable.getScope(t.val)); 
		FormalParams();
		return method;
	}

	void MethodBlock(MethodStatement method) {
		Expect(8);
		while (StartOf(5)) {
			if (StartOf(6)) {
				TreeNode node = DataItemDeclaration();
				method.add(node); 
			} else {
				TreeNode node = Statement();
				method.add(node); 
			}
		}
		Expect(9);
	}

	void ReturnType() {
		if (StartOf(4)) {
			StdType();
		} else if (la.kind == 23) {
			Get();
		} else SynErr(57);
	}

	void FormalParams() {
		Expect(12);
		if (StartOf(7)) {
			FormalParam();
			while (la.kind == 13) {
				Get();
				FormalParam();
			}
		}
		Expect(14);
	}

	void FormalParam() {
		Type();
		Expect(1);
	}

	TreeNode  Statement() {
		TreeNode  node;
		node = null; 
		if (la.kind == 8) {
			node = Block();
		} else if (la.kind == 6) {
			Get();
		} else if (isAssignment()) {
			node = Assignment();
			Expect(6);
		} else if (la.kind == 1) {
			node = MethodCall();
			Expect(6);
		} else if (la.kind == 24) {
			Get();
			Expect(12);
			IfStatement ifs = new IfStatement(null); 
			Expression expression = Expression();
			ifs.setWhen(expression); 
			Expect(14);
			BlockStatement block = Block();
			ifs.setThen(block); 
			if (la.kind == 25) {
				Get();
				block = Block();
				ifs.setElsedo(block); node = ifs; 
			}
		} else if (la.kind == 26) {
			Get();
			Expect(12);
			Expression expression = Expression();
			Expect(14);
			node = Statement();
		} else if (la.kind == 27) {
			Get();
			node = Statement();
			Expect(26);
			Expect(12);
			Expression expression = Expression();
			Expect(14);
			Expect(6);
		} else if (la.kind == 28) {
			Get();
			if (la.kind == 1) {
				Get();
			}
			Expect(6);
		} else if (la.kind == 29) {
			Get();
			if (la.kind == 1) {
				Get();
			}
			Expect(6);
		} else if (la.kind == 30) {
			Get();
			node = new ReturnStatement(); 
			if (StartOf(8)) {
				Expression expression = Expression();
				((ReturnStatement)node).setExpression(expression); 
			}
			Expect(6);
		} else SynErr(58);
		return node;
	}

	void StdType() {
		if (StartOf(9)) {
			NumType();
		} else if (la.kind == 18) {
			Get();
		} else SynErr(59);
	}

	void NumType() {
		if (la.kind == 20 || la.kind == 21 || la.kind == 22) {
			IntType();
		} else if (la.kind == 19) {
			Get();
		} else SynErr(60);
	}

	void IntType() {
		if (la.kind == 20) {
			Get();
		} else if (la.kind == 21) {
			Get();
		} else if (la.kind == 22) {
			Get();
		} else SynErr(61);
	}

	BlockStatement  Block() {
		BlockStatement  node;
		node = new BlockStatement(); 
		Expect(8);
		while (StartOf(10)) {
			TreeNode stmt = Statement();
			node.add(stmt); 
		}
		Expect(9);
		return node;
	}

	Assignment  Assignment() {
		Assignment  assignment;
		TreeNode node = Designator();
		assignment = new Assignment(node.getReference()); 
		Expect(11);
		Expression expression = Expression();
		assignment.setExpression(expression); 
		return assignment;
	}

	TreeNode  MethodCall() {
		TreeNode  node;
		node = null; 
		Expect(1);
		Expect(12);
		if (StartOf(8)) {
			List params = ActualParams();
		}
		Expect(14);
		return node;
	}

	List<Expression>  ActualParams() {
		List<Expression>  params;
		params = new LinkedList<Expression>(); 
		Expression expression = Expression();
		params.add(expression); 
		while (la.kind == 13) {
			Get();
			expression = Expression();
			params.add(expression); 
		}
		return params;
	}

	TreeNode  Designator() {
		TreeNode  node;
		Expect(1);
		node = new TreeNode(symbolTable.get(t.val)); 
		return node;
	}

	Expression  OrElseExpression() {
		Expression  left;
		left = AndThenExpression();
		while (la.kind == 31) {
			Get();
			Expression right = AndThenExpression();
			left = new OrElseExpression(left, right); 
		}
		return left;
	}

	Expression  AndThenExpression() {
		Expression  left;
		left = OrExpression();
		while (la.kind == 32) {
			Get();
			Expression right = OrExpression();
			left = new AndThenExpression(left, right); 
		}
		return left;
	}

	Expression  OrExpression() {
		Expression  left;
		left = XorExpression();
		while (la.kind == 33) {
			Get();
			Expression right = XorExpression();
			left = new OrExpression(left, right); 
		}
		return left;
	}

	Expression  XorExpression() {
		Expression  left;
		left = AndExpression();
		while (la.kind == 34) {
			Get();
			Expression right = AndExpression();
			left = new XorExpression(left, right); 
		}
		return left;
	}

	Expression  AndExpression() {
		Expression  left;
		left = EqualExpression();
		while (la.kind == 35) {
			Get();
			Expression right = EqualExpression();
			left = new AndExpression(left, right); 
		}
		return left;
	}

	Expression  EqualExpression() {
		Expression  left;
		left = RelExpression();
		while (la.kind == 36 || la.kind == 37) {
			if (la.kind == 36) {
				Get();
			} else {
				Get();
			}
			String operator = t.val; 
			Expression right = RelExpression();
			left = new EqualExpression(left, right, operator); 
		}
		return left;
	}

	Expression  RelExpression() {
		Expression  left;
		left = ShiftExpression();
		while (StartOf(11)) {
			if (la.kind == 38) {
				Get();
			} else if (la.kind == 39) {
				Get();
			} else if (la.kind == 40) {
				Get();
			} else {
				Get();
			}
			String operator = t.val; 
			Expression right = ShiftExpression();
			left = new RelExpression(left, right, operator); 
		}
		return left;
	}

	Expression  ShiftExpression() {
		Expression  left;
		left = AddExpression();
		while (la.kind == 42 || la.kind == 43 || la.kind == 44) {
			if (la.kind == 42) {
				Get();
			} else if (la.kind == 43) {
				Get();
			} else {
				Get();
			}
			String operator = t.val; 
			Expression right = AddExpression();
			left = new ShiftExpression(left, right, operator); 
		}
		return left;
	}

	Expression  AddExpression() {
		Expression  left;
		left = MulExpression();
		while (la.kind == 45 || la.kind == 46) {
			if (la.kind == 45) {
				Get();
			} else {
				Get();
			}
			String operator = t.val; 
			Expression right = MulExpression();
			left = new AddExpression(left, right, operator); 
		}
		return left;
	}

	Expression  MulExpression() {
		Expression  left;
		left = Unary();
		while (la.kind == 47 || la.kind == 48 || la.kind == 49) {
			if (la.kind == 47) {
				Get();
			} else if (la.kind == 48) {
				Get();
			} else {
				Get();
			}
			String operator = t.val; 
			Expression right = Unary();
			left = new MulExpression(left, right, operator); 
		}
		return left;
	}

	Expression  Unary() {
		Expression  unary;
		unary = new Unary("+");
		Unary current = (Unary)unary; 
		while (la.kind == 46 || la.kind == 50 || la.kind == 51) {
			if (la.kind == 46) {
				Get();
			} else if (la.kind == 50) {
				Get();
			} else {
				Get();
			}
			current.setNode(new Unary(t.val));
			current = (Unary)current.getNode(); 
		}
		TreeNode node = Primary();
		current.setNode(node); 
		return unary;
	}

	TreeNode  Primary() {
		TreeNode  node;
		node = null; 
		if (StartOf(12)) {
			node = Literal();
		} else if (isMethodCall()) {
			node = MethodCall();
		} else if (la.kind == 1) {
			node = Designator();
		} else if (la.kind == 12) {
			Get();
			node = Expression();
			Expect(14);
		} else SynErr(62);
		return node;
	}

	TreeNode  Literal() {
		TreeNode  node;
		node = null; 
		if (la.kind == 2) {
			Get();
			node = new Constant(Integer.parseInt(t.val)); 
		} else if (la.kind == 4) {
			Get();
			node = new Constant(Character.getNumericValue(t.val.charAt(0))); 
		} else if (la.kind == 3) {
			Get();
			node = new Constant(t.val); 
		} else if (la.kind == 52) {
			Get();
			node = new Constant(true); 
		} else if (la.kind == 53) {
			Get();
			node = new Constant(false); 
		} else SynErr(63);
		return node;
	}



	public void Parse() {
		la = new Token();
		la.val = "";		
		Get();
		TinyJava();
		Expect(0);

	}

	private static final boolean[][] set = {
		{T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, T,x,T,x, x,x,x,x, x,T,T,T, T,T,T,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,T,T, T,T,T,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,T,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,T,x,x, x,x,T,x, T,x,T,x, x,x,x,x, x,T,T,T, T,T,T,x, T,x,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,T,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,T,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,T,T,T, T,x,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,T,T, T,T,x,x},
		{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,T,x,x, x,x,T,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,x,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x},
		{x,x,T,T, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, T,T,x,x}

	};
} // end Parser


class Errors {
	public int count = 0;                                    // number of errors detected
	public java.io.PrintStream errorStream = System.out;     // error messages go to this stream
	public String errMsgFormat = "-- line {0} col {1}: {2}"; // 0=line, 1=column, 2=text
	
	protected void printMsg(int line, int column, String msg) {
		StringBuffer b = new StringBuffer(errMsgFormat);
		int pos = b.indexOf("{0}");
		if (pos >= 0) { b.delete(pos, pos+3); b.insert(pos, line); }
		pos = b.indexOf("{1}");
		if (pos >= 0) { b.delete(pos, pos+3); b.insert(pos, column); }
		pos = b.indexOf("{2}");
		if (pos >= 0) b.replace(pos, pos+3, msg);
		errorStream.println(b.toString());
	}
	
	public void SynErr (int line, int col, int n) {
		String s;
		switch (n) {
			case 0: s = "EOF expected"; break;
			case 1: s = "ident expected"; break;
			case 2: s = "number expected"; break;
			case 3: s = "stringconst expected"; break;
			case 4: s = "charconst expected"; break;
			case 5: s = "\"package\" expected"; break;
			case 6: s = "\";\" expected"; break;
			case 7: s = "\"class\" expected"; break;
			case 8: s = "\"{\" expected"; break;
			case 9: s = "\"}\" expected"; break;
			case 10: s = "\"final\" expected"; break;
			case 11: s = "\"=\" expected"; break;
			case 12: s = "\"(\" expected"; break;
			case 13: s = "\",\" expected"; break;
			case 14: s = "\")\" expected"; break;
			case 15: s = "\"[\" expected"; break;
			case 16: s = "\"]\" expected"; break;
			case 17: s = "\"ISR\" expected"; break;
			case 18: s = "\"boolean\" expected"; break;
			case 19: s = "\"char\" expected"; break;
			case 20: s = "\"byte\" expected"; break;
			case 21: s = "\"short\" expected"; break;
			case 22: s = "\"int\" expected"; break;
			case 23: s = "\"void\" expected"; break;
			case 24: s = "\"if\" expected"; break;
			case 25: s = "\"else\" expected"; break;
			case 26: s = "\"while\" expected"; break;
			case 27: s = "\"do\" expected"; break;
			case 28: s = "\"break\" expected"; break;
			case 29: s = "\"continue\" expected"; break;
			case 30: s = "\"return\" expected"; break;
			case 31: s = "\"||\" expected"; break;
			case 32: s = "\"&&\" expected"; break;
			case 33: s = "\"|\" expected"; break;
			case 34: s = "\"^\" expected"; break;
			case 35: s = "\"&\" expected"; break;
			case 36: s = "\"==\" expected"; break;
			case 37: s = "\"!=\" expected"; break;
			case 38: s = "\"<\" expected"; break;
			case 39: s = "\">\" expected"; break;
			case 40: s = "\"<=\" expected"; break;
			case 41: s = "\">=\" expected"; break;
			case 42: s = "\"<<\" expected"; break;
			case 43: s = "\">>\" expected"; break;
			case 44: s = "\">>>\" expected"; break;
			case 45: s = "\"+\" expected"; break;
			case 46: s = "\"-\" expected"; break;
			case 47: s = "\"*\" expected"; break;
			case 48: s = "\"/\" expected"; break;
			case 49: s = "\"%\" expected"; break;
			case 50: s = "\"~\" expected"; break;
			case 51: s = "\"!\" expected"; break;
			case 52: s = "\"true\" expected"; break;
			case 53: s = "\"false\" expected"; break;
			case 54: s = "??? expected"; break;
			case 55: s = "invalid ClassItemDeclaration"; break;
			case 56: s = "invalid Type"; break;
			case 57: s = "invalid ReturnType"; break;
			case 58: s = "invalid Statement"; break;
			case 59: s = "invalid StdType"; break;
			case 60: s = "invalid NumType"; break;
			case 61: s = "invalid IntType"; break;
			case 62: s = "invalid Primary"; break;
			case 63: s = "invalid Literal"; break;
			default: s = "error " + n; break;
		}
		printMsg(line, col, s);
		count++;
	}

	public void SemErr (int line, int col, String s) {	
		printMsg(line, col, s);
		count++;
	}
	
	public void SemErr (String s) {
		errorStream.println(s);
		count++;
	}
	
	public void Warning (int line, int col, String s) {	
		printMsg(line, col, s);
	}
	
	public void Warning (String s) {
		errorStream.println(s);
	}
} // Errors


class FatalError extends RuntimeException {
	public static final long serialVersionUID = 1L;
	public FatalError(String s) { super(s); }
}
